# 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
# 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None  # 既然是父节点的指针，难道不应该是previous吗？

# 思路：首先，找到这个树的根节点，然后中序遍历他，然后记录下来这个顺序值，然后找到当前节点所处的位置，然后返回数组下一个就行了

class Solution:
    def __init__(self):
        self.res = []

    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return pNode
        root = self.find_root(pNode)
        self.order_middle(root )
        for i in range(len(self.res)):
            if self.res[i] == pNode:
                if i<len(self.res)-1:
                    return self.res[i+1]
                else:
                    return None

    def find_root(self, my_node):
        while my_node.next:
            my_node = my_node.next
        return my_node

    def order_middle(self, my_node):
        if not my_node:
            return []
        self.order_middle(my_node.left)
        self.res.append(my_node)
        self.order_middle(my_node.right)


# 解法2：
class Solution1:
    def GetNext(self, pNode):
        # write code here
        if pNode.right:#有右子树
            p=pNode.right
            while p.left:
                p=p.left
            return p
        while pNode.next:#无右子树，则找第一个当前节点是父节点左孩子的节点
            if(pNode.next.left==pNode):
                return pNode.next
            pNode = pNode.next#沿着父节点向上遍历
        return  #到了根节点仍没找到，则返回空

node1 = TreeLinkNode(1)
node2 = TreeLinkNode(2)
node3 = TreeLinkNode(3)
node4 = TreeLinkNode(4)
node5 = TreeLinkNode(5)
node6 = TreeLinkNode(6)
node7 = TreeLinkNode(7)

node1.left = node2
node1.right = node3
node2.left = node4
node4.right = node5
node5.left = node6
node5.right = node7

sol = Solution()
sol.order_middle(node1)
for i in sol.res:
    print(i.val)
